package com.hdu.point_offer;

import java.util.ArrayList;
import java.util.List;

public class lcr153 {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    class Solution {

        List<Integer> path = new ArrayList<>();
        List<List<Integer>> ans = new ArrayList<>();

        public List<List<Integer>> pathTarget(TreeNode root, int target) {
            f(root, 0, target);
            return ans;
        }

        void f(TreeNode root, int curSum, int target) {
            if (root == null) return;
            if (isChild(root) && curSum + root.val == target)
            {
                path.add(root.val);
                ans.add(new ArrayList<>(path));
                path.remove(path.size() - 1);
                return;
            }
            path.add(root.val);
            f(root.left, curSum + root.val, target);
            f(root.right, curSum + root.val, target);
            path.remove(path.size() - 1);
        }

        boolean isChild(TreeNode root) {
            return root.left == null && root.right == null;
        }
    }
}
